Digital filters are electronic devices that accept a sequence of digital data samples and produce a modified sequence that is a linear combination of previous input data and output data. The data sequence is often obtained from a continuous analog waveform that has been digitized at predetermined (possibly uniform) time intervals. Sampling at uniform time intervals is often used because it simplifies analysis of the system performance. One relationship between the input and output of a digital filter that is often used is ##EQU1## where {x.sub.m } is the input data sequence, {y.sub.n } is the output data sequence and {h.sub.m } is a sequence of filter coefficients, sometimes called the impulse response of the filter. When h.sub.m has only a finite number of non-zero terms, the filter is said to have a finite impulse response (FIR filter). Otherwise, the filter is said to have an infinite impulse response (IIR filter). Often, the output data sequence {y.sub.n } is written as a linear combination of the input data sequence {x.sub.m } and preceding values of the output sequence, viz. ##EQU2## A filter of this type is said to be recursive and has infinite impulse response unless all coefficients of the second sum are zero, in which case the filter becomes an FIR filter.
The above remarks apply to one-dimensional filtering in which the data sequence may be related to a single increasing variable such as time. In other situations it is necessary to perform two-dimensional, or more generally n-dimensional, filtering of a data sequence that can only be represented by specification of two or more independent, monotonically increasing or decreasing variables. In this situation, one speaks of doing two-dimensional, or more generally n-dimensional, filtering. An example of such a prescription is the following: ##EQU3##
With reference to equation 1, if the upper limit M in the sum is finite, the filter is said to have a finite window of length M; this is the maximum length of a string of consecutive non-zero filter coefficients h.sub.k. This concept extends easily to two-dimensional or n-dimensional filtering. With reference to equation 3 above, Table 1 indicates the extent of a representative two-dimensional rectangular filter window. In two or more dimensions, a window need not be rectangular in shape, and one occasionally finds those of triangular shape or trapezoidal or other shape in problems encountered in nature. Where two-dimensional, or more generally n-dimensional, filtering is used, one problem encountered is the differing time delays in computation of terms that contribute to the same output term, where processing is distributed over a plurality of processors. The invention disclosed herein provides one technique for handling this problem.
TABLE 1 ______________________________________ 0 0 0 0 0 . . . 0 0 0 h.sub.0,0 h.sub.0,1 h.sub.1,2 h.sub.0,3 . . . h.sub.0,N-1 0 0 h.sub.1,0 h.sub.1,1 h.sub.1,2 h.sub.1,3 . . . h.sub.1,N-1 0 0 h.sub.2,0 h.sub.2,1 h.sub.2,2 h.sub.2,3 . . . h.sub.2,N-1 0 0 . . . 0 h.sub.M-1,0 h.sub.M-1,1 h.sub.M-1,2 h.sub.M-1,3 . . . h.sub.M-1,N-1 0 0 0 0 0 0 . . . 0 0 0 0 0 0 0 . . . 0 0 ______________________________________
In another embodiment, the invention provides apparatus for a digital signal processor array that can be reconfigured as a one-dimensional or as a two-dimensional array.